package com.leetcode.hashprimeMap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: ZhouBert
 * @date: 2019/9/29
 * @description:	49. 字母异位词分组
 * B
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 *
 * 示例:
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * 输出:
 * [
 *   ["ate","eat","tea"],
 *   ["nat","tan"],
 *   ["bat"]
 * ]
 * 说明：
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GroupAnagrams49 {

	static Map<Character,Integer> primeMap=new HashMap<>();

	static {
		primeMap.put('a', 2);
		primeMap.put('b', 3);
		primeMap.put('c', 5);
		primeMap.put('d', 7);
		primeMap.put('e', 11);
		primeMap.put('f', 13);
		primeMap.put('g', 17);
		primeMap.put('h', 19);
		primeMap.put('i', 23);
		primeMap.put('j', 29);
		primeMap.put('k', 31);
		primeMap.put('l', 37);
		primeMap.put('m', 41);
		primeMap.put('n', 43);
		primeMap.put('o', 47);
		primeMap.put('p', 53);
		primeMap.put('q', 59);
		primeMap.put('r', 61);
		primeMap.put('s', 67);
		primeMap.put('t', 71);
		primeMap.put('u', 73);
		primeMap.put('v', 79);
		primeMap.put('w', 83);
		primeMap.put('x', 89);
		primeMap.put('y', 97);
		primeMap.put('z', 101);
	}

	/**
	 * 建立一个好的 hash 函数，让 hash(字母异位词) 相同
	 * 	问题是如何定义好的函数呢？
	 * todo:通过素数
	 * todo:12 ms,在所有 Java 提交中击败了 98.15%,41.7 MB 在所有 Java 提交中击败了 98.19%
	 * @param strs
	 * @return
	 */
	public static List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> result=new ArrayList<>();
		if (strs==null||strs.length==0){
			return result;
		}

		///1.定义素数：
		// 2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101
		// a  b  c  d  e  f    g   h  i   j   k   l   m   n   o   p   q  r   s   t   u   v   w   x   y   z
		//放在 全局变量中

		///存储 Long-List<String> 下一步组装 List<List<String>>
		Map<Long, List<String>> temp=new HashMap<>();
		for (String item:
			 strs) {
			long tHash=hash(item);
			if (temp.containsKey(tHash)){
				temp.get(tHash).add(item);
			}else {
				ArrayList<String> tempList = new ArrayList<>();
				tempList.add(item);
				temp.put(tHash, tempList);
			}
		}

		///遍历 temp 组装结果
		for (Map.Entry<Long, List<String>> item:
		temp.entrySet()){
			result.add(item.getValue());
		}
		return result;
	}

	public static long hash(String str){
		char[] chars = str.toCharArray();
		long result=1;
		for (Character c :
				chars) {
			result*=primeMap.get(c);
		}
		return result;
	}

	public static void main(String[] args) {
		String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
		List<List<String>> lists = groupAnagrams(strs);
		System.out.println(lists);
	}
}
